#ifndef _math_fraction_h_
#define _math_fraction_h_

#include<iostream>
#include<stdint.h>
#include<stdlib.h>
#include<math/gcd.h>
#include<assert.h>

namespace contest
{
/**
 * A way to represent rational numbers without loss of precision.
 * @TODO: Should we parametrize this class?
 **/
class fraction
{
private:
    int64_t num;
    int64_t den;
    void reduce()
    {
        int64_t d = gcd(abs(num), abs(den));
        num /= d;
        den /= d;
    }
public:
    fraction(int64_t a): num(a), den(1)
    {
    }
    fraction(int64_t a, int64_t b): num(a), den(b)
    {
        reduce();
    }
    int64_t numerator() const
    {
        return num;
    }
    int64_t denominator() const
    {
        return den;
    }
    template <class I> fraction& operator *=(const I n)
    {
        num *= n;
        reduce();
        return *this;
    }
    template <class I> fraction operator *(const I n) const
    {
        fraction result = *this;
        result *= n;
        return result;
    }
    template <class I> fraction& operator /=(const I n)
    {
        den *= n;
        reduce();
        return *this;
    }
    template <class I> fraction operator /(const I n) const
    {
        fraction result = *this;
        result /= n;
        return result;
    }
    template <class I> fraction& operator +=(const I n)
    {
        num += den*n;
        reduce();
        return *this;
    }
    template <class I> fraction operator +(const I n) const
    {
        fraction result = *this;
        result += n;
        return result;
    }
    bool operator < (const fraction& rhs) const
    {
        if ((den >= 0 && rhs.den >= 0) ||
            (den <= 0 && rhs.den <= 0))
            return num * rhs.den < rhs.num * den;
        else
            return num * rhs.den > rhs.num * den;
    }
    bool operator == (const fraction& rhs) const
    {
        return num * rhs.den == rhs.num * den;
    }
    bool operator == (const int64_t& rhs) const
    {
        return num == rhs * den;
    }
    friend std::ostream& operator<<(std::ostream& out, const fraction& s)
    {
        std::cout<<s.num<<"/"<<s.den;
    }
};

void testFraction()
{
    assert(fraction(1) == 1);
    assert(fraction(2) == 2);
    assert(fraction(1, 2) == fraction(1, 2));
    assert(fraction(1, 6) + 1==fraction(7, 6));
    assert(fraction(1, 6) + 2==fraction(13, 6));
    assert(fraction(1, 2)*2 == 1);
    assert(fraction(2, 3)*2 == fraction(4, 3));
    assert(fraction(2, 6)*2 == fraction(2, 3));
    assert(fraction(2, 6)/3 == fraction(1, 9));
    assert(fraction(2, 1)/2 == 1);
    assert(fraction(1, 3) < fraction(1, 2));
}

}

#endif
